Data transmissions generally include extra information, submitted along with the data at a transmitter, which is used at the receiver to verify an error-free transmission. The extra information may, for example, be a cyclic redundancy check (CRC) code, a type of error identification code. A CRC engine at the transmitter generates the CRC code, then another CRC engine at the receiver checks the CRC code.
After the CRC engine is initialized with a seed value, polynomial, or modulus-based, arithmetic is performed on each data block to be transmitted, generating a CRC code for the data. In CRC-32B, for example, the transmitter CRC engine uses a 32-bit generator polynomial, X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5 +X4+X2+X1+X0, to operate upon the data block. The resulting CRC is appended to the end of the data block and a new block comprising both the data block and the CRC are transmitted to a receiving device. The polynomial arithmetic may be, for example, modulo-2, although any modulus-based arithmetic in which the modulus is a prime number may characterize CRC calculations.
At the receiver, the same 32-bit polynomial is used to operate upon the new block by the receiver CRC engine. Where the expected result is obtained, the data was transmitted successfully. Where the result is not the expected result, the retransmission of the damaged data block can be arranged. Some variation to the described scheme is possible, as CRC algorithms are employed in a wide array of data communications systems.
CRC engines are typically made up of digital logic such as flip-flops, for automatically generating and appending the CRC to the data stream (at the transmitting end) and, likewise, computing the CRC of the combined data and CRC block at the receiving end. CRC-32 may be implemented with a linear feedback shift register (LFSR) comprising multiple D flip-flops, as one example. Or, the modulo-2 arithmetic performed in each CRC engine may be implemented in firmware or other software programs. A combination of hardware and software solutions is also possible.
Advanced Technology Attachment (ATA) is a technology in which drive controllers are integrated onto disk drives. Serial ATA is a physical storage interface defining protocols for the internal attachment of storage devices. Under Serial ATA, a CRC check is used to verify packet transmission to or from the ATA device. A specific generator polynomial (CRC-32B) and a seed value (0×52325032) are used to calculate the CRC. (Serial ATA is a product of the Serial ATA Working Group. Specifications under Serial ATA are available at www.serialata.org.)
There is a new class of serial ATA devices used to route data between host ports and receiving devices. Referred to herein as routers, these new devices allow multiple entities to be connected to a single host port along a transmission interface. A routing header is prepended to each packet prior to transmission. The routing header indicates the path to which the packet is to be transmitted and thus identifies which device in the transmission interface is the intended recipient of the packet. When the router receives the packet, it reads the routing header and forwards the packet accordingly.
In efficient router designs, the routers include a small amount of buffering for the incoming packets. In some cases, the router may start to forward a packet to the next port before receiving the entire packet. Since the routing header tells the router where the packet is to be sent, the router will at least buffer the header information before forwarding the packet to the intended port. To ensure that the header is valid, a dedicated header CRC, generated at the transmitter, is appended after the routing header.
Once the router identifies the intended recipient of the packet, the routing header is modified to construct a reverse path back to the transmitting device. This allows the receiving device to identify the transmitting device and intended recipient of a response packet. Where the transmission path includes multiple routers, the routing header is updated multiple times. Likewise, the header CRC is updated each time the routing header is changed.
In traditional CRC design, the CRC is the residue (remainder) of the data to be protected (viewed as a polynomial) divided by a generator polynomial. If the packet is valid, the receiving device CRC engine will sum the CRC value and the CRC residue prior to the CRC field. Using modulo-2 arithmetic, these two values sum to an expected result if the packet is valid.
If traditional CRC design is used for both the routing header CRC and the data CRC, the CRC residue will be the expected result after the header CRC field. However, under Serial ATA, the initial seed for the CRC starting at the data field must be 0×52325032. In order for both statements to be true, the transmitting device CRC engine would have to reset or “re-seed” after calculating the header CRC, but before calculating the final CRC. The same would be true for the receiving device CRC engine. Hardware CRC engines could be re-designed to reset after processing the header CRC, but at an increase in cost. Further, each entity in the transmission interface would be expected to employ these re-designed CRC engines.
Traditional CRC design presents another limitation. With a packet including both a header CRC and a final CRC, if the final CRC applies to the entire packet, the final CRC will be re-calculated (at the router) following a change to the header. However, routers need the header CRC alone. If the final CRC applies to just the data portion of the packet, endpoints (hosts and devices) will perform CRC validation on both the header portion and the data portion, to ensure the validity of the entire packet. However, endpoints need the data CRC alone. Thus, under the traditional CRC design, the division of labor between the router and the endpoints is not reflected in performing CRC calculations.
It would be more efficient if the endpoint could check a single CRC that covers the entire packet. If the final CRC is used to cover the entire packet, the endpoint could ignore the header CRC field in determining the validity of the packet. No reset of the CRC engine would be necessary.
However, where the final CRC covers the entire packet, another problem is presented. Since each router in the point-to-point interface changes the header, the final CRC would have to be recomputed as well at the router. Each time a CRC is recalculated, there is a chance that a prior transmission error is inadvertently corrected. Thus, it would be preferable not to recalculate the final CRC at each router.
Thus, there is a need to transmit packets in a transmission interface such that the final CRC for each packet is calculated only at the original transmission point and unchanged thereafter, where the packets include a header that may be modified by an entity along the transmission interface (i.e., a dynamic header), wherein the header is also covered by a separate CRC.